/**
 *  二叉树的层序遍历，自己的题解
 */
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr){};
    TreeNode(int x) : val(x), left(nullptr), right(nullptr){};
    TreeNode(int x, TreeNode* left, TreeNode* right)
        : val(x), left(left), right(right){};
    void setVal(int x) { val = x; }
    void setAttribute(int x, TreeNode* l, TreeNode* r) {
        val = x;
        left = l;
        right = r;
    }
    void setChildren(TreeNode* l, TreeNode* r) {
        left = l;
        right = r;
    }
};

class Solution {
public:
    void wildTraversal(TreeNode* node, vector<int>& res) {
        queue<TreeNode*> queue;
        // 层次遍历
        if (node == nullptr) {
            return;
        }

        res.push_back(node->val);
        if (node->left != nullptr) {
            queue.push(node->left);
        }
        if (node->right != nullptr) {
            queue.push(node->right);
        }

        while (!queue.empty()) {
            TreeNode* top = queue.front();
            queue.pop();
            res.push_back(top->val);
            if (top->left != nullptr) {
                queue.push(top->left);
            }
            if (top->right != nullptr) {
                queue.push(top->right);
            }
        }
    }

    void show(TreeNode* node) {
        vector<int> res;
        wildTraversal(node, res);
        // 遍历输出res
        for (const auto& item : res) {
            cout << item << " ";
        }
    }
};

void test() {
    // 1. 构造一棵树。
    TreeNode* t1 = new TreeNode(1);
    TreeNode* t2 = new TreeNode(2);
    TreeNode* t3 = new TreeNode(3);
    TreeNode* t4 = new TreeNode(4);
    TreeNode* t5 = new TreeNode(5);
    TreeNode* t6 = new TreeNode(6);

    t1->setChildren(t2, t3);
    t2->setChildren(t4, t5);
    t5->setChildren(t6, nullptr);

    Solution s;
    s.show(t1);
}

int main() {
    test();
    return 0;
}